package day1_array.leetcode;

/**
 * @author yuisama
 * @date 2023年07月07日 15:00
 * @description
 */
public class Offer_53_2_MissingNumber {
    // 求和法
//    public int missingNumber(int[] nums) {
//        // 求出从1..n - 1的不缺失的元素之和
//        int sum = 0;
//        for (int i = 0; i <= nums.length; i++) {
//            sum += i;
//        }
//        // 求出当前数组实际元素之和
//        int actual = 0;
//        for (int i : nums) {
//            actual += i;
//        }
//        return sum - actual;
//    }
    // 二分法
    // 本题的关键就是如何二分整个区间
    // 若nums[mid] == mid，则缺失的元素在右半区间;反之，缺失的元素在左半区间!
    public int missingNumber(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] == mid) {
                // 缺失的元素在右半边
                l = mid + 1;
            }else {
                // 缺失的元素在左半边
                r = mid - 1;
            }
        }
        return l;
    }
}
